package Graph.graphWithWeight.MinistedTree.Kruskal;

import Graph.graphWithWeight.EdgeWeight;
import Graph.graphWithWeight.GraphWeight;

import java.util.ArrayList;
import java.util.Collections;

/**
 * @Author: 蔡翔
 * @Date: 2020/2/24 10:06
 * @Version 1.0
 *
 * 无向有权图 的最小生成树(定义权值最低的 边连成的一棵树)
 * 克鲁斯卡尔算法 就是在一个图中 一直找权值最小的边拼起来，不能拼成回路
 */
public class Kruskal {
    private GraphWeight G;
    //mst = 最小生成树
    private ArrayList<EdgeWeight> mst;
    public Kruskal(GraphWeight G){
        this.G = G;
        mst = new ArrayList<EdgeWeight>();
        ConnectComponent cc = new ConnectComponent(this.G);
        if(cc.count()>1){
            //如果联通分量 大于1 那么一定没有最小生成树
            return;
        }
        //Kruskal
        //首先对图中所有边进行一个排序
        ArrayList<EdgeWeight> edges = new ArrayList<>();
        for(int v =0;v<G.V();v++){
            for(int w:G.adj(v)){
                // 避免重复判断边，，因为是无向图 ，所以在邻接矩阵中有两条一样的边（这个方法比较巧妙用来筛选重复遍）
                if(v<w){
                    edges.add(new EdgeWeight(v,w,G.getWeight(v,w)));
                }
            }
        }
        Collections.sort(edges);

        UF uf = new UF(G.V());
        for(EdgeWeight edge:edges){
            int v = edge.getV();
            int w = edge.getW();
            //只要避免出现环 ，就可以防止 选择了两条同等效应的边
            if(!uf.isConnected(v,w)){
                mst.add(edge);
                uf.unionElements(v,w);
            }
        }
    }

    public ArrayList<EdgeWeight> result(){
        return mst;
    }

    public static void main(String[] args) {
        GraphWeight graphWeight = new GraphWeight("gWeight.txt");
        Kruskal kruskal = new Kruskal(graphWeight);
        System.out.println(kruskal.result());
    }

}
